#ifndef GAMEENGINE_GEOMETRY_PARALLELOGRAM2D_HPP
#define GAMEENGINE_GEOMETRY_PARALLELOGRAM2D_HPP

#ifdef GAMEENGINE_NAMESPACES
namespace GameEngine {
#endif

//=================================================================================
// Implementation of the Parallelogram2d class

//! Default constructor
/*!
 @note Class T should have a default constructor
 */
template <class T>
Parallelogram2d<T>::Parallelogram2d() {}

//! Constructor from an origin and two vectors
/*!
 @param origin The origin of the parallelogram
 @param v1 The first vector of the parallelogram
 @param v2 The second vector of the parallelogram
 @note Class T should have a copy constructor
 */
template <class T>
Parallelogram2d<T>::Parallelogram2d(const Point2d<T>& origin, const Vector2d<T>& v1, const Vector2d<T>& v2) :
	origin_(origin), v1_(v1), v2_(v2) {}

//! Copy constructor
/*!
 @param rhs The parallelogram to copy
 @note Class T should have a copy constructor
 */
template <class T>
Parallelogram2d<T>::Parallelogram2d(const Parallelogram2d& rhs) :
	origin_(rhs.origin_), v1_(rhs.v1_), v2_(rhs.v2_) {}

//! Destructor
/*!
 @note The destructor of class T should be public
 */
template <class T>
Parallelogram2d<T>::~Parallelogram2d() {}

//! Assignment operator
/*!
 @param rhs The parallelogram to copy
 @note Class T should have an assignment operator
 */
template <class T>
Parallelogram2d<T>& Parallelogram2d<T>::operator=(const Parallelogram2d& rhs) {
	if ( &rhs != this ) {
		origin_ = rhs.origin_;
		v1_ = rhs.v1_;
		v2_ = rhs.v2_;
	}
	return *this;
}

//! Accessor to the origin of the parallelogram (read-write)
/*!
 @return A reference to the origin of the parallelogram
 */
template <class T>
Point2d<T>& Parallelogram2d<T>::origin() {
	return origin_;
}

//! Accessor to the origin of the parallelogram (read only)
/*!
 @return A constant reference to the origin of the parallelogram
 */
template <class T>
const Point2d<T>& Parallelogram2d<T>::origin() const {
	return origin_;
}

//! Accessor to the first vector (read-write)
/*!
 @return A reference to the first vector
 */
template <class T>
Vector2d<T>& Parallelogram2d<T>::v1() {
	return v1_;
}

//! Accessor to the first vector (read only)
/*!
 @return A constant reference to the first vector
 */
template <class T>
const Vector2d<T>& Parallelogram2d<T>::v1() const {
	return v1_;
}

//! Accessor to the second vector (read-write)
/*!
 @return A reference to the second vector
 */
template <class T>
Vector2d<T>& Parallelogram2d<T>::v2() {
	return v2_;
}

//! Accessor to the second vector (read only)
/*!
 @return A constant reference to the second vector
 */
template <class T>
const Vector2d<T>& Parallelogram2d<T>::v2() const {
	return v2_;
}

//! Compute the point along the parallelogram at given parametric coordinates
/*!
 @param coords The parametric coordinates along the parallelogram axes
 @return The point along the parallelogram at given parametric coordinates
 */
template <class T>
Point2d<T> Parallelogram2d<T>::point(const Coords2d<T>& coords) const {
	return Point2d<T>(
				origin_.x() + coords.u()*v1_.x() + coords.v()*v2_.x(),
				origin_.y() + coords.u()*v1_.y() + coords.v()*v2_.y()
			);
}

//! Compute the parametric coordinates of given point along the parallelogram
/*!
 *  Each time this function is called, a transformer has to be created. If you want
 *  to convert multiple points to parametric coordinates, it is much more efficient
 *  to directly access the transformer and use the transform() function.
 *
 @param pt The point whose parametric coordinates should be computed
 @return The parametric coordinates of the given point
 */
template <class T>
Coords2d<T> Parallelogram2d<T>::coordinates(const Point2d<T>& pt) const {
	Transformer2d<T> t = transformer();
	Point2d<T> tmp = t.transform(pt);
	return Coords2d<T>(tmp.x(), tmp.y());
}

//! Build a transformer that converts points in the Cartesian space to parametric coordinates
/*!
 @return A transformer that converts points in the Cartesian space to parametric coordinates
 */
template <class T>
Transformer2d<T> Parallelogram2d<T>::transformer() const {
	return Transformer2d<T>(origin_, point(Coords2d<T>(1,0)), point(Coords2d<T>(0,1)),
		Point2d<T>(0,0), Point2d<T>(1,0), Point2d<T>(0,1));
}

//! Compute the location of the given point
/*!
 @return The given point
 */
template <class T>
Point2d<T> Parallelogram2d<T>::operator[](Parallelogram2D::Index index) const {
	if ( index == Parallelogram2D::First ) return origin_;
	if ( index == Parallelogram2D::Second ) return point(Coords2d<T>(1,0));
	if ( index == Parallelogram2D::Third ) return point(Coords2d<T>(0,1));
	return point(Coords2d<T>(1,1));
}

//! Test wether a point is inside the parallelogram
/*!
 @param rhs The point to test for inclusion
 @param strict If set to true, a point located exactly on the perimeter of
			   the parallelogram is not considered to belong to the parallelogram
 @return True if the point is inside the parallelogram, false otherwise
 */
template <class T>
bool Parallelogram2d<T>::inside(const Point2d<T>& rhs, bool strict) const {
	// Get the four parallelogram points
	const Point2d<T>& p1 = origin_;
	Point2d<T> p2 = point(Coords2d<T>(1,0));
	Point2d<T> p3 = point(Coords2d<T>(1,1));
	Point2d<T> p4 = point(Coords2d<T>(0,1));

	// Get the sides of the parallelogram
	T d1 = (p2.x()-p1.x())*(rhs.y()-p1.y()) - (p2.y()-p1.y())*(rhs.x()-p1.x());
	T d2 = (p3.x()-p2.x())*(rhs.y()-p2.y()) - (p3.y()-p2.y())*(rhs.x()-p2.x());
	T d3 = (p4.x()-p3.x())*(rhs.y()-p3.y()) - (p4.y()-p3.y())*(rhs.x()-p3.x());
	T d4 = (p1.x()-p4.x())*(rhs.y()-p4.y()) - (p1.y()-p4.y())*(rhs.x()-p4.x());

	// Check the parallelogram belonging
	if ( strict ) {
		// Check whether point lies on one of the (extended) parallelogram edges
		// If it does, point does not strictly belong to the parallelogram
		if ( d1 == 0 ) return false;
		if ( d2 == 0 ) return false;
		if ( d3 == 0 ) return false;
		if ( d4 == 0 ) return false;

		// Check the sides
		if ( ( d1 < 0 ) != ( d2 < 0 ) ) return false;
		if ( ( d1 < 0 ) != ( d3 < 0 ) ) return false;
		if ( ( d1 < 0 ) != ( d4 < 0 ) ) return false;
	}
	else {
		// Get the first non-null cross product (i.e., the first edge along which point does not lie)
		T d = ( d1 == 0 ? ( d2 == 0 ? ( d3 == 0 ? d4 : d3 ) : d2 ) : d1 );

		// Check the sides if and only if point is not on the edge
		if ( ( d1 != 0 ) && ( ( d <= 0 ) != ( d1 <= 0 ) ) ) return false;
		if ( ( d2 != 0 ) && ( ( d <= 0 ) != ( d2 <= 0 ) ) ) return false;
		if ( ( d3 != 0 ) && ( ( d <= 0 ) != ( d3 <= 0 ) ) ) return false;
		if ( ( d4 != 0 ) && ( ( d <= 0 ) != ( d4 <= 0 ) ) ) return false;
	}

	// If all sides are the same, point is in the parallelogram
	return true;
}


//! Compute the intersection between the line and the parallelogram
/*!
 @param rhs The line to intersect with the parallelogram
 @param line_coordinate1 The parametric line coordinate of the first intersection between
                         the parallelogram and the line, if both do intersect. To
					     retrieve the intersection point, call rhs.point(line_coordinate1)
 @param line_coordinate2 The parametric line coordinate of the second intersection between
                         the parallelogram and the line, if both do intersect. To
					     retrieve the intersection point, call rhs.point(line_coordinate2)
 @param type If not nil, this parameter receives the type of intersection
             between the parallelogram and the line. The intersection type
			 can be:<BR>
			 NoIntersection if the line does not intersect the parallelogram,<BR>
			 Intersection if the line intersects the parallelogram
 @return The number of intersections between the line and the parallelogram
 */
template <class T>
int Parallelogram2d<T>::intersection( const Line2d<T>& rhs, T& line_coordinate1, T& line_coordinate2, IntersectionType::Type* type) const
{
	int res = 0;

	// Get the four parallelogram points
	const Point2d<T>& p1 = origin_;
	Point2d<T> p2 = point(Coords2d<T>(1,0));
	Point2d<T> p3 = point(Coords2d<T>(1,1));
	Point2d<T> p4 = point(Coords2d<T>(0,1));

	// Test the first line
	{{
		Line2d<T> line(p1, p2);
		T tmp_coord;
		IntersectionType::Type tmp_type = rhs.intersection(line, tmp_coord);
		if ( tmp_type == IntersectionType::Intersection ) {
			if ( ( tmp_coord >= 0 ) && ( tmp_coord <= 1 ) ) {
				line_coordinate1 = tmp_coord;
				++res;
			}
		}
	}}

	// Test the second line
	{{
		Line2d<T> line(p2, p3);
		T tmp_coord;
		IntersectionType::Type tmp_type = rhs.intersection(line, tmp_coord);
		if ( tmp_type == IntersectionType::Intersection ) {
			if ( ( tmp_coord >= 0 ) && ( tmp_coord <= 1 ) ) {
				if ( res == 0 ) line_coordinate1 = tmp_coord;
				else line_coordinate2 = tmp_coord;
				++res;
			}
		}
	}}

	// Test the third line
	{{
		if ( res < 2 ) {
			Line2d<T> line(p3, p4);
			T tmp_coord;
			IntersectionType::Type tmp_type = rhs.intersection(line, tmp_coord);
			if ( tmp_type == IntersectionType::Intersection ) {
				if ( ( tmp_coord >= 0 ) && ( tmp_coord <= 1 ) ) {
					if ( res == 0 ) line_coordinate1 = tmp_coord;
					else line_coordinate2 = tmp_coord;
					++res;
				}
			}
		}
	}}

	// Test the fourth line
	{{
		if ( res < 2 ) {
			Line2d<T> line(p4, p1);
			T tmp_coord;
			IntersectionType::Type tmp_type = rhs.intersection(line, tmp_coord);
			if ( tmp_type == IntersectionType::Intersection ) {
				if ( ( tmp_coord >= 0 ) && ( tmp_coord <= 1 ) ) {
					if ( res == 0 ) line_coordinate1 = tmp_coord;
					else line_coordinate2 = tmp_coord;
					++res;
				}
			}
		}
	}}

	if ( type ) *type = ( ( res > 0 ) ? IntersectionType::Intersection : IntersectionType::NoIntersection );
	return res;
}

//! Compute the parametric coordinates of the closest point along the parallelogram
/*!
 @param rhs The point to project on the parallelogram
 @param coords Receives the parametric coordinates of the closest point along the parallelogram
 @return True if parametric coordinates of the closest point could be computed (this function
         should return false only if the parallelogram is degenerate)
 @note If you want to get back to the point location, call the point(coords) function
 */
template <class T>
bool Parallelogram2d<T>::closest_point(const Point2d<T>& rhs, Coords2d<T>& coords) const {
	// Get the four parallelogram points
	Point2d<T> pts[] = {
		origin_,
		point(Coords2d<T>(1,0)),
		point(Coords2d<T>(1,1)),
		point(Coords2d<T>(0,1))
	};

	// Find the two closest points
	int index1 = 0, index2 = 1;
	if ( rhs.get_square_distance(pts[0]) > rhs.get_square_distance(pts[1]) ) {
		index1 = 1;
		index2 = 0;
	}
	if ( rhs.get_square_distance(pts[index2]) > rhs.get_square_distance(pts[2]) ) {
		if ( rhs.get_square_distance(pts[index1]) > rhs.get_square_distance(pts[2]) ) {
			index2 = index1;
			index1 = 2;
		}
		else {
			index2 = 2;
		}
	}
	if ( rhs.get_square_distance(pts[index2]) > rhs.get_square_distance(pts[3]) ) {
		index2 = 3;
	}

	// Test if point falls out of the line
	Line2d<T> closest_line(pts[index1], pts[index2]);
	T param = closest_line.closest_point(rhs);
	if ( param <= 0 ) {
		if ( index1 == 0 ) {
			coords = Coords2d<T>(0,0);
			return true;
		}
		if ( index1 == 1 ) {
			coords = Coords2d<T>(1,0);
			return true;
		}
		if ( index1 == 2 ) {
			coords = Coords2d<T>(1,1);
			return true;
		}
		coords = Coords2d<T>(0,1);
		return true;
	}
	if ( param >= 1 ) {
		if ( index2 == 0 ) {
			coords = Coords2d<T>(0,0);
			return true;
		}
		if ( index2 == 1 ) {
			coords = Coords2d<T>(1,0);
			return true;
		}
		if ( index2 == 2 ) {
			coords = Coords2d<T>(1,1);
			return true;
		}
		coords = Coords2d<T>(0,1);
		return true;
	}

	// Test if point falls in the line
	Coords2d<T> res(0,0);
	if ( index1 == 1 ) res.u() += ( (T)1.0 - param );
	else if ( index1 == 2 ) {
		// TODO - check
		res.u() += param;
		res.v() += ( (T)1.0 - param );
	}
	else if ( index1 == 2 ) res.v() += ( (T)1.0 - param );
	if ( index2 == 1 ) res.u() += param;
	else if ( index2 == 2 ) {
		// TODO - check
		res.u() += ( (T)1.0 - param );
		res.v() += param;
	}
	else if ( index2 == 3 ) res.v() += param;

	// Return closest point
	coords = res;
	return true;
}

//! Compute the closest point along the parallelogram
/*!
 @return The closest point along the parallelogram
 @param rhs The point to project on the parallelogram
 @note This is an overloaded function, provided for convenience and for compatibility
       with some template classes. It is slower than the function
	   closest_point(const Point2d<T>& rhs, Coords2d<T>& coords). Unless you explicitly
	   need the point location, its use is therefore not advised
 */
template <class T>
Point2d<T> Parallelogram2d<T>::closest_point(const Point2d<T>& rhs) const {
	// Get the point coordinates
	Coords2d<T> coordinates;
	closest_point(rhs, coordinates);

	// Return the point location
	return point(coordinates);
}

//! Compute the perimeter of the parallelogram
/*!
 @return The perimeter of the parallelogram
 */
template <class T>
T Parallelogram2d<T>::perimeter() const {
	return (T)2*v1_.length() + (T)2*v2_.length();
}

//! Compute the area of the parallelogram
/*!
 @return The area of the parallelogram
 */
template <class T>
T Parallelogram2d<T>::area() const {
	T tmp = (points_[1].x()-points_[0].x())*(points_[2].y()-points_[0].y())
		  - (points_[1].y()-points_[0].y())*(points_[2].x()-points_[0].x())
	return ( ( tmp >= 0 ) ? tmp : -tmp );
}

//! Check if the parallelogram is degenerate
/*!
 @return True if the parallelogram is degenerate, false otherwise
 @note The parallelogram is considered degenerate if its area is equal
       or below the tolerance threshold
 */
template <class T>
bool Parallelogram2d<T>::degenerate(const T& tolerance) const {
	return ( area() <= tolerance );
}

//! Check if the coordinates are in the parallelogram
/*!
 @param coords The parametric coordinates to test
 @param strict If set to true, points located on the edges of the parallelogram
               are not considered to belong to the parallelogram
 @return True if the coordinates are in the parallelogram, false otherwise
 */
template <class T>
bool Parallelogram2d<T>::in_parallelogram(const Coords2d<T>& coords, bool strict) {
	if ( strict ) return ( ( coords.u() >  0 ) && ( coords.v() >  0 ) && ( coords.u() <  1 ) && ( coords.v() <  1 ) );
	/* else */    return ( ( coords.u() >= 0 ) && ( coords.v() >= 0 ) && ( coords.u() <= 1 ) && ( coords.v() <= 1 ) );
}

#ifdef GAMEENGINE_NAMESPACES
} // namespace GameEngine
#endif

#endif
